1. Field of the Invention
The invention relates in general to the technical domain of cryptography and more especially to a procedure for improved protection of a cryptographic calculation against attacks. The invention is provided in particular for use in portable data carriers, which can be configured as smart cards in different forms of construction or as chip modules, for example.
2. Description of the Related Art
The RSA method, described, e.g. in U.S. Pat. No. 4,405,829, is well known for the exchange of encrypted and/or signed data. According to the RSA method, a public key is used for encryption or signature verification and a secret private key for decryption or signature generation. Security of the RSA method is based on the fact that currently no efficient way of determining the prime factors p and q of a large number n with n=p·q is known. Whereas the so-called modulus n is published as part of the public key, the values p and q must be kept secret.
The calculation processes required for executing the RSA method are relatively complicated. For instance, the data to be processed have to be exponentiated with parameters of the private key during decryption or signature generation, for example. In particular for portable data carriers with their limited computing power, an implementation of the RSA method for decryption or signature generation is therefore frequently employed which uses the CRT (Chinese remainder theorem) and therefore is also designated as RSA-CRT method. By using the RSA-CRT method the required computing expenditure is reduced by approximately the factor 4.
The RSA-CRT method provides, instead of one complicated power calculation, to perform two far simpler exponentiations, the results of which are then combined into the decrypted data or the generated signature. Only the secret prime factor p enters into the first of these calculations and only the secret prime factor q into the second calculation.
Attack scenarios have been proposed, in which exactly one of the two named RSA-CRT calculation branches is interfered with, e.g. by deliberate action of heat or radiation or by electrical pulses. If this succeeds, a multiple of the prime factor p, q, whose calculation branch has not been interfered with can be derived from the result of the overall calculation. In other words, conclusions can be drawn as to the private key by means of the described attack. This has potentially catastrophic consequences, because not only the decryption or signature generation just performed, but all the cryptographic operations executed using the private key are compromised.
The attack just mentioned is known by the name “fault attack” or “Bellcore attack” and described, e.g., in column 4 of U.S. Pat. No. 5,991,415. Likewise in U.S. Pat. No. 5,991,415 a method is disclosed, in which an additional factor j enters into the calculation to protect against this attack which takes place during the cryptographic calculation. However, as will be shown below, there are further possibilities of attack, against which nothing can be done by the method known from U.S. Pat. No. 5,991,415.
Said possibility of attack is particularly critical if the cryptographic calculation is executed by a processor of a portable data carrier, for example a smart card or a chip module. A first reason for this is that portable data carriers of this kind are often used for security-critical applications, e.g. in connection with financial transactions, access control or the signature of legally binding documents. Secondly, portable data carriers are typically in the possession of the attacker while the cryptographic calculation is being executed, so this person has every opportunity to influence the calculation and to spy on the results of the calculation.